117. 填充每个节点的下一个右侧节点指针 II

Similar Question

leading to the advanced question

Solution Tips

这次必须依赖 depth 了

方案一: DFS

  var connect = function (root) {
    if (root == null) return root
  
    if (root.left != null) {
      if (root.right != null) {
        // 若右子树不为空，则左子树的 next 即为右子树
        root.left.next = root.right
      } else {
        // 若右子树为空，则左子树的 next 由根节点的 next 得出，next为根节点的父节点的右子树
        root.left.next = nextNode(root.next)
      }
    }
    if (root.right != null) {
      // 右子树的 next 由根节点的 next 得出
      root.right.next = nextNode(root.next)
    }
    // 先确保 root.right 下的节点的已完全连接，因 root.left 下的节点的连接
    // 需要 root.next 下的节点的信息，root.next肯定是祖先的右子树
    // 若 root.next 下的节点未完全连
    // 接（即先对 root.left 递归），则 root.next 下的信息链不完整，将
    // 返回错误的信息。可能出现的错误情况如下图所示。此时，底层最左边节点将无
    // 法获得正确的 next 信息：
    //                  o root
    //                 / \
    //     root.left  o —— o  root.right
    //               /    / \
    //              o —— o   o
    //             /        / \
    //            o        o   o
    connect(root.right)
    connect(root.left)
    return root
  
    function nextNode(node) {
      while (node != null) {
        if (node.left != null) return node.left
        if (node.right != null) return node.right
        node = node.next
      }
      return null
    }
  }

方案二: BFS

  var connect = function(root) {
    if(root == null)return root;
    const queue = [root]
    while(queue.length>0){
      let cur = null
      // 一次读取一整行的node，静态化
      const size = queue.length
      for(let i=0;i<size;i++){
        const temp = queue.shift()
        if(cur !=null) cur.next = temp
        cur = temp
        // 这里改变了队列的长度，所以前面必须静态化
        if(temp.left!=null) queue.push(temp.left)
        if(temp.right!=null) queue.push(temp.right)
      }
    }
    return root
  }

方案三: BFS + 链表优化

Loading Question... - 力扣（LeetCode）

    public Node connect(Node root) {
        if (root == null)
            return root;
        //cur我们可以把它看做是每一层的链表
        Node cur = root;
        while (cur != null) {
            //遍历当前层的时候，为了方便操作在下一
            //层前面添加一个哑结点（注意这里是访问
            //当前层的节点，然后把下一层的节点串起来）
            Node dummy = new Node(0);
            //pre表示访下一层节点的前一个节点
            Node pre = dummy;
            //然后开始遍历当前层的链表
            while (cur != null) {
                if (cur.left != null) {
                    //如果当前节点的左子节点不为空，就让pre节点
                    //的next指向他，也就是把它串起来
                    pre.next = cur.left;
                    //然后再更新pre
                    pre = pre.next;
                }
                //同理参照左子树
                if (cur.right != null) {
                    pre.next = cur.right;
                    pre = pre.next;
                }
                //继续访问这一行的下一个节点
                cur = cur.next;
            }
            //把下一层串联成一个链表之后，让他赋值给cur，
            //后续继续循环，直到cur为空为止
            cur = dummy.next;
        }
        return root;
    }